struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
  ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
    ListNode resHead{0, nullptr}, *tailPtr = &resHead;
    while (list1 != nullptr && list2 != nullptr) {
      if (list1->val > list2->val) {
        tailPtr->next = list2;
        list2 = list2->next;
      } else {
        tailPtr->next = list1;
        list1 = list1->next;
      }
      tailPtr = tailPtr->next;
    }
    if (list1 != nullptr) {
      tailPtr->next = list1;
    }
    if (list2 != nullptr) {
      tailPtr->next = list2;
    }
    return resHead.next;
  }
};
